import java.util.*;


public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        // -准备示例数据
        ArrayList<ArrayList<Integer>> sampleList = new ArrayList<>();
        ArrayList<Integer> sampleData = new ArrayList<>();
        sampleData.add(5);
        sampleData.add(10);
        sampleList.add(sampleData);

        sampleData = new ArrayList<>();
        sampleData.add(3);
        sampleData.add(1);
        sampleList.add(sampleData);

        // -示例数据没有问题
        // for(int i = 0; i < sampleList.size(); i++) {
        //     for(int j = 0; j < sampleList.get(0).size(); j++) {
        //         System.out.print(sampleList.get(i).get(j) + " ");
        //     }
        //     System.out.println();
        // }
        System.out.println(test.knapsack(6, 2, sampleList));
    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param v int整型 
     * @param n int整型 
     * @param nums int整型ArrayList<ArrayList<>> 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> knapsack (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        /**
         * 完全背包问题
         * 第一问：求这个背包至多能装多大价值的物品
         * 状态表示：
         *  dp[i][j]表示在以i下标为结尾的物品中挑选，使其体积不超过j，此时背包所能装的最大价值
         * 状态转移方程：
         *
         * 初始化：
         *
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  dp[n][v]
         * 第二问：若是背包恰好装满，求这个背包至多能装多大价值物品
         * 状态表示
         *  full[i][j]表示在以i下标为结尾的物品中挑选，使其体积等于j，此时背包所能装的最大价值
         * 状态转移方程：
         *
         * */
        // 1 创建dp表
        int[][] dp = new int[n+1][v+1];
        int[][] fu = new int[n+1][v+1];
        // 2 初始化

        // 3 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= v; j++) {
                // 第一问
                dp[i][j] = dp[i-1][j];
                if(j >= nums.get(i-1).get(0)) {
                    // -取各种情况下的最大值
                    dp[i][j] = Math.max(
                            Math.max(dp[i-1][j-nums.get(i-1).get(0)], dp[i][j-nums.get(i-1).get(0)]) + nums.get(i-1).get(1),
                            dp[i][j]
                    );
                }
                // 第二问
                fu[i][j] = fu[i-1][j];
                // -这个判断添加为：满足j>=c 并且 前者目标体积能够组合
                if(j >= nums.get(i-1).get(0) &&
                        (
                                j == nums.get(i-1).get(0)
                                || fu[i][j-nums.get(i-1).get(0) ] != 0
                                || fu[i-1][j-nums.get(i-1).get(0) ] != 0
                        )
                ) {
                    int tempValue = Math.max(fu[i][j-nums.get(i-1).get(0) ], fu[i-1][j-nums.get(i-1).get(0) ]) + nums.get(i-1).get(1);
                    fu[i][j] = Math.max(tempValue, fu[i][j]);
                }
            }
        }
        // 4 返回值
        ArrayList<Integer> retList = new ArrayList<>();
        retList.add(dp[n][v]);
        retList.add(fu[n][v]);
        return retList;
    }
}